#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int DataType;
typedef struct Node
{
    DataType data;     // 数据域
    struct Node *next; // 指针域
} Node, *LinkList;

/**
 * 初始化带头结点的单链表
 */
void initListWithHead(LinkList *L)
{
    *L = (Node *)malloc(sizeof(Node));
    if (*L == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(1);
    }
    (*L)->next = NULL;
}

/**
 * 初始化不带头结点的单链表
 */
void initListWithoutHead(LinkList *L)
{
    *L = NULL; // 不带头结点的链表初始为空
}

/**
 * 带头结点的单链表按照位序插入元素,时间复杂度O(n)
 */
bool insertListWithHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }

    int j = 0;
    Node *p = *L;

    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        return false;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        return false;
    }

    q->data = e;
    q->next = p->next;
    p->next = q;

    return true;
}

/**
 * 不带头结点的单链表按照位序插入元素,时间复杂度O(n)
 */
bool insertListWithoutHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }
    //===============此处有区别start====================
    if (i == 1)
    {
        Node *q = (Node *)malloc(sizeof(Node));
        if (q == NULL)
        {
            fprintf(stderr, "内存分配失败\n");
            return false;
        }
        q->data = e;
        q->next = *L;
        *L = q;
        return true;
    }

    int j = 1;
    //==============end=====================
    Node *p = *L;

    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        return false;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        return false;
    }

    q->data = e;
    q->next = p->next;
    p->next = q;

    return true;
}

/**
 * 单链表后插操作,在p节点之后插入元素e,时间复杂度O(1)
 */
bool InsertNextNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        printf("分配内存失败\n");
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
/**
 * 单链表前插操作,在p节点之前插入元素e,时间复杂度O(1)
 */
bool InsertPriorNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;
    s->data = p->data; // 交换数据
    p->data = e;       // 交换数据
    return true;
}

/**
 * 单链表前插操作,在p节点之前插入节点s,时间复杂度O(1)
 */
bool InsertPriorNode1(Node *p, Node *s)
{
    if (p == NULL || s == NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;
    DataType temp;
    temp = s->data;
    s->data = p->data;
    p->data = temp;
    return true;
}

/**
 * 按位序删除带头节点,最坏,平均时间复杂度O(n),最好时间复杂度O(1)
 */
bool ListDelete(LinkList *L, int i, DataType *e)
{
    if (i < 1)
    {
        return false;
    }
    int j = 0;    // 指针位序
    Node *p = *L; // p指针指向头结点
    while (p != NULL && j < i - 1)
    { // 找到要删除的节点的前一个节点
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    if (p->next == NULL)
    {
        return false;
    }
    Node *q = p->next; // q指向被删除的节点
    *e = q->data;      // 把要删除的数据赋值给传进来的e

    p->next = q->next; // 要删除的节点的 前一个节点连接后一个节点

    free(q); // 释放要删除的q节点

    return true;
}

/**
 * 删除指定节点
 */
bool DeleteNode(Node *p)
{
    if (p == NULL)
    {
        return false;
    }
    Node *q = p->next; // 令q指向p的后继结点
    p->data = q->data; // 后一个节点的值赋值给要删除的节点
    p->next = q->next; // 上一个节点指向删除节点的后一个节点
    free(q);           // 释放q
    return true;
}

/**
 * 打印单链表
 */
void printList(LinkList L)
{
    Node *current = L;
    while (current != NULL)
    {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main()
{
    LinkList L1, L2;

    // 初始化带头结点的链表
    initListWithHead(&L1);
    // 测试插入函数
    insertListWithHead(&L1, 1, 100);
    insertListWithHead(&L1, 2, 200);
    insertListWithHead(&L1, 3, 300);
    insertListWithHead(&L1, 1, 1100);

    printf("带头结点的链表:\n");
    printList(L1->next); // 从头结点的下一个节点开始打印
    int e;
    ListDelete(&L1, 5, &e);
    printf("带头结点的链表删除后:\n");
    printf("e: %d\n", e);
    printList(L1->next); // 从头结点的下一个节点开始打印

    // 初始化不带头结点的链表
    initListWithoutHead(&L2);
    // 测试插入函数
    insertListWithoutHead(&L2, 1, 100);
    insertListWithoutHead(&L2, 2, 200);
    insertListWithoutHead(&L2, 3, 300);
    insertListWithoutHead(&L2, 1, 1100);

    printf("不带头结点的链表:\n");
    printList(L2);

    return 0;
}